package leetcode.dandiaostk;

public class A962 {
    public int maxWidthRamp(int[] nums) {
//对于新加入元素，如果比前面小，可能和后面构成答案，如果比前面大，那么不可能构成答案
        //6 0
        int length=nums.length;
        int[] stk=new int[length];
        int hh=0;//栈内元素
        for(int i=0;i<length;i++){
            if(hh==0||nums[i]<nums[stk[hh-1]]){
                //入栈
                stk[hh++]=i;
            }
        }
        //栈内元素都可能为答案的左侧
        //反向遍历
        //保持栈顶元素被满足条件且在靠右侧的元素使用
        int res=0;
        for(int i=length-1;i>=0;i--){
            //如果栈内有元素，该元素大于等于栈顶元素，记录答案,栈顶出
            while(hh>=1&&nums[i]>=nums[stk[hh-1]]){
                res=Math.max(res,i-stk[hh-1]);
                hh--;
            }
        }
        return res;
    }
}
